%a summary of your design approach and implementation
\section{Implementation details}
\subsection{Main data structures}
\begin{itemize}
\item \textbf{Board:} Contains the internal representation of a Sokoban board. This class represents the problem as a bi-dimensional matrix of BoardElement, which is an enumeration defined to better represent the characters that define the board. This class also contains many auxiliary structures that are useful to optimize the algorithms, such as a list of all the boxes, free goals and occupied goals. Also, a series of methods where developed to manipulate the board. The most important ones were:

	\begin{itemize}
	\item \textbf{calculateDistancesForAllEmptyGoals:} Performs the calculation of the heuristic value in each of the positions of the board.
	\item \textbf{commitPath:} Performs the necessary modifications on the board in order to simulate a series of movements taken by the agent.
	\item \textbf{commitTunnel:} Moves a particular box through a tunnel and does the modifications that this implies on the board.
	\item \textbf{computeTunnels:} Calculates all the tunnels that are made by walls on the board.
	\item \textbf{getKey:} Gets the value used to hash the board.
	\item \textbf{isFinal:} Checks if the board is in a final state, which means that every box is on some goal.
	\end{itemize}

\item \textbf{Client:} Contains all the instructions necessary to receive a board and compute a solution. Some of the most important methods in this class are:

	\begin{itemize}
	\item \textbf{findPath:} Uses a BFS strategy to get the shortest set of movements to get from one place to another in the board
	\item \textbf{findSolution:} Combines all the algorithms and optimizations that have been described to find a valid solution to a given board.
	\end{itemize}

\item \textbf{Node:} Is used to represent elements in different search trees. It contains useful information that can be set using it's constructors so the search will be natural and fast.
\end{itemize}

\subsection{Well-known algorithms implemented}
\begin{itemize}
\item \textbf{A*:} Was used to improve the convergence of the search tree used to look for a solution to the problem. The memory used in the algorithm was represented by the path that was taken to get to the particular configuration. The heuristic value used was the lower bound that the board had for the amount of movements necessary to find a solution.
\item \textbf{Shortest path BFS:} Used to find the shortest set of movements to get from one position in the board to another.
\item \textbf{Tree marking BFS:} Used to find the upper-left corner of the reachable space of the player. This was a very helpful method when creating the keys used for hashing the boards.
\end{itemize}